25D - Roads not only in Berland - CodeForces Solution

dsu graphs trees *1900

Please click on ads to support us..

Python Code: 

class DSU:
    def __init__(self, n: int):
        self.n = n
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, u: int) -> int:
        if u == self.parent[u]:
            return u
        self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u: int, v: int):
        u, v = self.find(u), self.find(v)
        if u != v:
            if self.size[u] < self.size[v]:
                u, v = v, u
            self.parent[v] = u
            self.size[u] += self.size[v]


def solve():
    n = int(input())
    dsu = DSU(n)
    removes = []
    for _ in range(n - 1):
        u, v = map(int, input().split())
        pu, pv = dsu.find(u), dsu.find(v)
        if pu == pv:
            removes.append((u, v))
        dsu.union(pu, pv)
    uniques = list(set([dsu.find(i) for i in range(1, n + 1)]))
    sz = len(uniques)
    if sz < 2:
        print(0)
        return
    else:
        print(sz - 1)
        for i in range(sz - 1):
            day = [removes[i][0], removes[i][1], uniques[i], uniques[i+1]]
            print(*day)


solve()

C++ Code: 

#include <bits/stdc++.h>

using namespace std;

class DSU {
 public:
  vector<int> P;
  vector<int> rank;

  DSU(int n) {
    P.resize(n);
    rank.resize(n, 0);
    for (int i = 0; i < n; i++) {
      P[i] = i;
    }
  }

  void join(int u, int v) {
    int pu = P[u];
    int pv = P[v];

    if (pu == pv) {
      return;
    }

    if (rank[pu] < rank[pv]) {
      swap(pu, pv);
    }

    if (rank[pu] == rank[pv]) {
      rank[pu]++;
    }

    P[pv] = pu;
  }

  int get(int u) {
    if (P[u] != u) {
      P[u] = get(P[u]);
    }
    return P[u];
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n;
  cin >> n;

  DSU dsu(n + 1);
  vector<vector<int>> ans;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    if (dsu.get(u) != dsu.get(v)) {
      dsu.join(u, v);
    } else {
      vector<int> spare = {u, v, 0, 0};
      ans.push_back(spare);
    }
  }

  int k = 0;
  for (int i = 1; i < n; i++) {
    if (dsu.get(i) != dsu.get(i + 1)) {
      dsu.join(i, i + 1);
      ans[k][2] = i;
      ans[k][3] = i + 1;
      k++;
    }
  }

  cout << k << "\n";
  for (auto &row : ans) {
    for (int a : row) {
      cout << a << " ";
    }
    cout << "\n";
  }
}


Comments

Submit
0 Comments
More Questions

898A - Rounding
1372B - Omkar and Last Class of Math
1025D - Recovering BST
439A - Devu the Singer and Churu the Joker
1323A - Even Subset Sum Problem
1095A - Repeating Cipher
630F - Selection of Personnel
630K - Indivisibility
20B - Equation
600B - Queries about less or equal elements
1015A - Points in Segments
1593B - Make it Divisible by 25
680C - Bear and Prime 100
1300A - Non-zero
1475E - Advertising Agency
1345B - Card Constructions
1077B - Disturbed People
653A - Bear and Three Balls
794A - Bank Robbery
157A - Game Outcome
3B - Lorry
1392A - Omkar and Password
489A - SwapSort
932A - Palindromic Supersequence
433A - Kitahara Haruki's Gift
672A - Summer Camp
1277A - Happy Birthday Polycarp
577A - Multiplication Table
817C - Really Big Numbers
1355A - Sequence with Digits